package com.godme.string;

import java.util.HashMap;
import java.util.Objects;

public class Trie {



    HashMap<Character, Trie> nodes = new HashMap<>();
    Character character;
    boolean isLeaf = false;

    public Trie(Character character) {
        this.character = character;
    }


    public void insert(String string){
        doInsert(this, string, 0);
    }

    public void doInsert(Trie trie, String string, int index){
        if(index >= string.length()){
            trie.isLeaf = true;
            return;
        }
        Character c = string.charAt(index);
        Trie childTrie = trie.nodes.computeIfAbsent(c, k->new Trie(c));
        doInsert(childTrie, string, index+1);
    }

    public boolean containsWords(String target){
        Trie subTrie = nodes.get(target.charAt(0));
        return subTrie.doContain(target, 0);
    }

    public boolean doContain(String target, int depth){
        if(Objects.isNull(target)){
            return false;
        }
        if(target.length() == depth+1){
            return isLeaf;
        }
        char c = target.charAt(depth);
        if(c != character){
            return false;
        }

        Trie child = nodes.get(target.charAt(depth+1));
        if(Objects.isNull(child)){
            return false;
        }
        return child.doContain(target, depth+1);
    }

    public void printWords(){
        doPrint(this.character+"");
    }


    public void doPrint(String prefix){
        if(isLeaf){
            System.err.println(prefix);
        }
        if(nodes.isEmpty()){
            return;
        }
        nodes.values().forEach(e-> e.doPrint(prefix + e.character));
    }

    public static void main(String[] args) {
        Trie t = new Trie(' ');

        t.insert("how");
        t.insert("hi");
        t.insert("hello");
        t.insert("her");
        t.insert("he");
        t.printWords();
        System.err.println("===============");
        System.err.println(t.containsWords("hello"));
    }







}
